Problem statement: zenit15cke

Ešte jednu partiu?

Počet bodov: 30, časový limit: 500ms

Miša chytila piškvorková mánia. Cez prestávky, cez hodiny, proste hocikedy schytí neboráka spolužiaka, štvorčekový zošit a ide sa na vec.

Po týždni hrania sa však Mišovi zdalo, že začal nejako príliš často prehrávať. Dačo tu smrdí. Preto by rád skontroloval, či v odohraných partiách niekto nepodvádzal.

Úloha

Vašou úlohou je zistiť, či zadaná partia piškvoriek mohla vzniknúť platnými ťahmi bez podvádzania. Piš-kvorky majú nasledujúce pravidlá:

• Hráči striedavo označujú prázdne políčka mriežky svojimi znakmi.
• Začínajúci hráč používa krížiky (X), druhý krúžky(O).
• Hra končí, keď niektorý hráč vytvorí súvislú radu piatich svojich znakov v riadku, stĺpci, alebo diagonálne.
• Hra končí remízou, keď sa plocha zaplní bez výhry niektorého hráča.

Vstup a výstup

Na prvom riadku dostanete dve medzerou oddelené čísla. \(r\) \((1 \leq r \leq 100)\) – počet riadkov a \(c\) – počet stĺpcov mapy \((1 \leq c \leq 100)\).

Na nasledujúcich \(r\) riadkoch dostanete partiu piškvoriek.

Každý riadok je tvorený \(c\) znakmi – X, O alebo .(prázdne políčko).

Ak hra nemohla vzniknúť platnou postupnosťou ťahov, vypíšte PODVODNIK!. Inak vypíšte Prvy vyhral, Druhy vyhral alebo Remiza podľa toho, kto vyhral. Ak hra mohla vzniknúť postupnosťou platných ťahov, no nie je dokončená (nikto nevyhral a plocha nie je zaplnená), tak vypíšte Prvy na tahu alebo Druhy na tahu podľa toho, ktorý hráč by mal ťahať ako ďalší.

Príklad

Input:

6 6
...OX.
..OXO.
.OXX..
.X.O..
X.....
O..X..

Output:

Prvy vyhral

Input:

6 6
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO
OOOOOO

Output:

PODVODNIK!